package sjg.tenNormalAlgorithm.kmp;

import java.util.Arrays;

/**
 * KMP算法
 * 步骤：
 * 1. 先根据给定的匹配字符串生成 部分匹配表
 * 2. 从首位开始匹配，匹配不到的时候，根据 已匹配的数值-最后一位匹配的值对应的部分匹配表中的值的得到下个匹配的位置
 */
public class KMPAlgorithm {
    public static void main(String[] args) {
        String str1 = "BBC ABCDAB ABCDABCDABDE";
        String str2 = "ABCDABD";

        int[] next = kmpNext(str2);
        System.out.println("next= " + Arrays.toString(next));

        int i = kmpSearch(str1, str2, next);
        System.out.println("匹配到的索引值为：" + i);
    }

    /**
     * 获取一个字符串的 **部分匹配表**
     */
    private static int[] kmpNext(String dest) {
        //创建一个next 数组保存部分匹配值
        int[] next = new int[dest.length()];
        next[0] = 0; //如果字符串是长度为1 部分匹配值就是0
        for (int i = 1, j = 0; i < dest.length(); i++) {
            // 当 dest.charAt(i) != dest.charAt(j)，需要从dest[j-1]获取新的j
            // 直到发现 有 dest.charAt(i) == dest.charAt(j)成立才退出
            // KMP核心代码
            while (j > 0 && dest.charAt(i) != dest.charAt(j)) { // 作用： 从当前位置往前重置j
                j = next[j - 1];
            }
            if (dest.charAt(i) == dest.charAt(j)) { // 相等时 -> j递增
                j++;
            }
            next[i] = j;
        }

        return next;
    }

    /**
     * hsp
     * "BBC ABCDAB ABCDABCDABDE";
     * "ABCDABD";
     */
    private static int kmpSearch(String str1, String str2, int[] next) {
        //遍历
        for (int i = 0, j = 0; i < str1.length(); i++) {

            //需要处理 str1.charAt(i) ！= str2.charAt(j), 去调整j的大小
            //KMP算法核心点
            while (j > 0 && str1.charAt(i) != str2.charAt(j)) {
                j = next[j - 1];
            }

            if (str1.charAt(i) == str2.charAt(j)) {
                j++;
            }
            if (j == str2.length()) {// 匹配到值，直接返回
                return i - j + 1;
            }
        }
        return -1;
    }

}
